#include <vector>

using namespace std;

// 同时运行N台电脑的最长时间
// 你有 n 台电脑。给你整数 n 和一个下标从 0 开始的整数数组 batteries
// 其中第 i 个电池可以让一台电脑 运行 batteries[i] 分钟
// 你想使用这些电池让 全部 n 台电脑 同时 运行。
// 一开始，你可以给每台电脑连接 至多一个电池
// 然后在任意整数时刻，你都可以将一台电脑与它的电池断开连接，并连接另一个电池，你可以进行这个操作 任意次
// 新连接的电池可以是一个全新的电池，也可以是别的电脑用过的电池
// 断开连接和连接新的电池不会花费任何时间。
// 注意，你不能给电池充电。
// 请你返回你可以让 n 台电脑同时运行的 最长 分钟数。
// 测试链接 : https://leetcode.cn/problems/maximum-running-time-of-n-computers/

class Solution 
{
private:
    // 让 n 台电脑共同运行 time 分钟，能不能做到
    bool f(vector<int>& batteries, int n, long time)
    {
        // 碎片电量总和
        long sum = 0;
        for(int x : batteries)
        {
            if(x > time) --n;
            else sum += x; // x <= time，是碎片电池
            // 碎片电量 >= 台数 * 要求
            if(sum >= (long)n * time) return true;
        }
        return false;
    }

public:
    // 单纯的二分答案法
	// 时间复杂度 O(n * log(sum))，额外空间复杂度 O(1)
    long long maxRunTime(int n, vector<int>& batteries) 
    {
        long sum = 0;
        for(int x : batteries) sum += x;
        long ans = 0;
        // [0, sum] 上不停二分
        long l = 0, r = sum;
        while(l <= r)
        {
            // m 中点，让 n 台电脑共同运行 m 分钟，能不能做到
            long m = l + (r - l) / 2;
            if(f(batteries, n, m))
            {
                ans = m;
                l = m + 1;
            }
            else r = m - 1;
        }
        return ans;
    }
};



class Solution 
{
private:
    // 让 n 台电脑共同运行 time 分钟，能不能做到
    bool f(vector<int>& batteries, int n, int time)
    {
        // 碎片电量总和
        long sum = 0;
        for(int x : batteries)
        {
            if(x > time) --n;
            else sum += x; // x <= time，是碎片电池
            // 碎片电量 >= 台数 * 要求
            if(sum >= (long)n * time) return true;
        }
        return false;
    }

public:
	// 二分答案法 + 增加分析(贪心)
	// 时间复杂度O(n * log(max))，额外空间复杂度O(1)
    long long maxRunTime(int n, vector<int>& batteries) 
    {
        long sum = 0;
        int mx = 0;
        for(int x : batteries)
        {
            sum += x;
            mx = max(mx, x);
        }

        // 就是增加了这里的逻辑
        // 所有电池的最大电量是 mx
        // 如果此时 sum > (long) max * num，
        // 说明 : 最终的供电时间一定在 >= mx，而如果最终的供电时间 >= mx
        // 说明 : 对于最终的答案 X 来说，所有电池都是课上讲的"碎片拼接"的概念
        // 那么寻找 ? * num <= sum 的情况中，尽量大的 ? 即可
        // 即 sum / num
        if(sum > (long)n * mx) return sum / n;

        // 最终的供电时间一定在 < mx 范围上
		// [0, sum] 二分范围，可能定的比较粗，虽然不影响，但毕竟是有点慢
		// [0, mx] 二分范围！更精细的范围，二分次数会变少
        long ans = 0;
        // [0, sum] 上不停二分
        long l = 0, r = mx;
        while(l <= r)
        {
            // m 中点，让 n 台电脑共同运行 m 分钟，能不能做到
            long m = l + (r - l) / 2;
            if(f(batteries, n, m))
            {
                ans = m;
                l = m + 1;
            }
            else r = m - 1;
        }
        return ans;
    }
};